import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * 面试题52：两个链表的第一个公共节点
 */
public class Offer_52 {
    /**
     * 方法四：双指针
     * <p>
     * 时间复杂度：O(m+n)
     * <p>
     * 空间复杂度：O(1)
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ptrA = headA, ptrB = headB;
        while (ptrA != ptrB) {
            ptrA = (ptrA != null) ? ptrA.next : headB;
            ptrB = (ptrB != null) ? ptrB.next : headA;
        }
        return ptrA;
    }

    /**
     * 方法三：哈希表
     * <p>
     * 时间复杂度：O(m+n)
     * <p>
     * 空间复杂度：O(max(m,n))
     */
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();

        ListNode ptrA = headA, ptrB = headB;
        // 将链表 A 中的节点放入 set 中
        while (ptrA != null) {
            set.add(ptrA);
            ptrA = ptrA.next;
        }
        // 遍历链表 B
        while (ptrB != null) {
            // 链表 B 第一个在 set 中已存在的节点即是所求
            if (set.contains(ptrB)) {
                return ptrB;
            }
            ptrB = ptrB.next;
        }
        return null;
    }

    /**
     * 书中方法二：长链表先行
     * <p>
     * 时间复杂度：O(m+n)
     * <p>
     * 空间复杂度：O(1)
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode ptrA = headA, ptrB = headB;
        // 计算两个链表的长度
        int lenA = 0, lenB = 0;
        while (ptrA != null) {
            lenA++;
            ptrA = ptrA.next;
        }
        while (ptrB != null) {
            lenB++;
            ptrB = ptrB.next;
        }

        // 找出较长的链表
        ListNode longList = null, shortList = null;
        if (lenA > lenB) {
            longList = headA;
            shortList = headB;
        } else {
            longList = headB;
            shortList = headA;
        }

        // 两链表长度之差
        int diff = Math.abs(lenA - lenB);
        // 长链表先行 diff 步
        for (int i = 0; i < diff; i++) {
            longList = longList.next;
        }
        // 两个链表一起走，直到遇到第一个相同节点，即是所求
        while (longList != null && shortList != null && longList != shortList) {
            longList = longList.next;
            shortList = shortList.next;
        }
        return longList;
    }

    /**
     * 书中方法一：辅助栈
     * <p>
     * 时间复杂度：O(m+n)
     * <p>
     * 空间复杂度：O(m+n)
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        Deque<ListNode> stackA = new LinkedList<>();
        Deque<ListNode> stackB = new LinkedList<>();
        ListNode ptrA = headA, ptrB = headB;
        // 把两个链表的节点分别压入两个栈中，这样就能从尾部开始比较两个链表了
        while (ptrA != null) {
            stackA.push(ptrA);
            ptrA = ptrA.next;
        }
        while (ptrB != null) {
            stackB.push(ptrB);
            ptrB = ptrB.next;
        }

        ListNode ans = null;
        while (!stackA.isEmpty() && !stackB.isEmpty()) {
            if (stackA.peek() == stackB.peek()) {
                // 如果两个栈顶元素相同，则出栈，比较下一个栈顶
                ans = stackA.pop();
                stackB.pop();
                continue;
            } else {
                // 如果两个栈顶元素不同，则最后一个相同栈顶即是所求
                return ans;
            }
        }
        return ans;
    }
}
